package summary;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/4 19:45
 */
public class Title105 {

    class TreeNode{
        int val;

        TreeNode left;

        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    Map<Integer, Integer> hash;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        hash = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            hash.put(inorder[i], i);
        }
        return dfs(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode dfs(int[] preorder, int preorder_start, int preorder_end, int[] inorder, int inorder_start, int inorder_end) {
        if (preorder_end < preorder_start) {
            return null;
        }
        //根节点
        int rootValue = preorder[preorder_start];
        TreeNode root = new TreeNode(rootValue);
        //查找根节点在中序序列中的位置
        int rootIndex = hash.get(rootValue);
        //中序遍历
        int inorder_left_start = inorder_start;
        int inorder_left_end = rootIndex - 1;
        int inorder_right_start = rootIndex + 1;
        int inorder_right_end = inorder_end;
        //前序遍历
        int preorder_left_start = preorder_start + 1;
        int preorder_left_end = preorder_left_start + (inorder_left_end - inorder_left_start);
        int preorder_right_start = preorder_left_end + 1;
        int preorder_right_end = preorder_end;
        root.left = dfs(preorder, preorder_left_start, preorder_left_end, inorder, inorder_left_start, inorder_end);
        root.right = dfs(preorder, preorder_right_start, preorder_right_end, inorder, inorder_right_start, inorder_right_end);
        return root;
    }


    public static void main(String[] args) {

    }
}
